package com.leetcode.test.stack;

import org.junit.Assert;
import org.junit.Test;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 最小栈 https://leetcode-cn.com/explore/learn/card/queue-stack/218/stack-last-in-first-out-data-structure/877/
 * <p>
 * 参考答案：http://www.manongjc.com/article/49621.html
 */
public class Min {

	@Test
	public void min() {
		MinStack minStack = new MinStack();
		minStack.push(-2);
		minStack.push(0);
		minStack.push(-3);

		Assert.assertEquals(-3, minStack.getMin());   //--> 返回 -3.

		minStack.pop();

		Assert.assertEquals(0, minStack.top());      //--> 返回 0.
		Assert.assertEquals(-2, minStack.getMin());   //--> 返回 -2.
	}

	@Test
	public void min2() {
		MinStack minStack = new MinStack();
		minStack.push(0);
		minStack.push(1);
		minStack.push(0);

		Assert.assertEquals(0, minStack.getMin());

		minStack.pop();

		Assert.assertEquals(0, minStack.getMin());
	}

	// 左程云老师的  程序员代码面试指南
	public class MinStack {

		private Stack<Integer> stackData;//数据栈
		private Stack<Integer> stackMin;//保存当前最小数的栈（称最小栈

		//构造函数
		public MinStack() {
			stackData = new Stack<>();
			stackMin = new Stack<>();
		}

		//压人函数
		public void push(Integer num) {
			//压入时判断最小栈是否为空或者要压入的数是否比最小栈栈顶数还小，时则压入数据站的同时压入最小栈
			if (stackMin.isEmpty() || getMin() > num) {
				stackMin.push(num);
			} else {
				int newMin = getMin();
				stackMin.push(newMin);
			}
			stackData.push(num);
		}

		//弹出函数
		public void pop() {
//			Integer num = stackData.pop();
//			if (stackMin.peek() == num) {
//				stackMin.pop();
//			}
			stackMin.pop();
			stackData.pop();
		}

		// 获取栈中最小数
		public int getMin() {
			return stackMin.peek();
		}

		public int top() {
			return stackData.peek();
		}
	}

//	static class MinStack {
//
//		List<Integer> data;
//
//		/** initialize your data structure here. */
//		public MinStack() {
//			data = new ArrayList();
//		}
//
//		public void push(int x) {
//			data.add(x);
//		}
//
//		public void pop() {
//			if (data.isEmpty()) {
//				return;
//			}
//			data.remove(data.size() - 1);
//		}
//
//		public int top() {
//			return data.get(data.size() - 1);
//		}
//
//		public int getMin() {
//			Integer min = null;
//
//			for (int element : data) {
//				if (min == null) {
//					min = element;
//					continue;
//				}
//				min = Math.min(min, element);
//			}
//
//			return min;
//		}
//	}
}
